| contributor | FMI, Theoretische Informatik |
| creator | Lohrey, Markus |
| date | 2003-09-17 |
| description | 185 pages |
| The present work contains a treatise of several computational and logical aspects of infinite monoids. The first chapter is devoted to the word problem for finitely generated monoids. In particular, the relationship between the computational complexity of the word problem and the syntactical properties of monoid presentations is investigated. The second chapter studies Cayley-graphs of finitely generated monoids under a logical point of view. Cayley-graphs of groups play an important role in combinatorial group theory. We will study first-order and monadic second-order theories of Cayley-graphsfor both groups and monoids. The third chapter deals with word equations over monoids. Using the graph product operation, which generalizes both the free and the direct product, we generalize the seminal decidability results of Makaninon free monoids and groups to larger classes of monoids. | |
| format | application/pdf |
| 2434068 Bytes |
| identifier | http://www.informatik.uni-stuttgart.de/cgi-bin/NCSTRL/NCSTRL_view.pl?id=HABIL-2003-01&engl=1 |
| language | eng |
| publisher | Stuttgart, Germany, Universität Stuttgart |
| source | ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/HABIL-2003-01/HABIL-2003-01.pdf |
| subject | Grammars and Other Rewriting Systems (CR F.4.2) |
| Models of Computation (CR F.1.1) | |
| Complexity Measures and Classes (CR F.1.3) | |
| Mathematical Logic (CR F.4.1) | |
| Mathematical Logic | |
| Word problems | |
| Groups | |
| Monoids | |
| Decidability | |
| Complexity | |
| Cayley-graphs | |
| title | Computational and logical aspects of infinite monoids |
| type | Text |
| Postdoctoral Qualification |